#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
// 英语    抄博友程序    floyd扩展    背
int g[110][110];
int hinge[110][110];
int vis[110];
int main()
{
	while (1)
	{
		int n;
		cin >> n;
		if (n == 0)
		{
			break;
		}
		memset(hinge, 0, sizeof(hinge));
		memset(vis, 0, sizeof(vis));
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				char c;
				cin >> c;
				g[i][j] = c - '0';
			}
		}
		for (int k = 1; k <= n; k++)
		{
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					if (g[i][k] != 0 && g[k][j] != 0)
					{
						if (g[i][j] == 0 || g[i][j] > (g[i][k] + g[k][j]))
						{
							hinge[i][j] = k;
							g[i][j] = g[i][k] + g[k][j];
						}
						else if (g[i][j] == (g[i][k] + g[k][j]))
						{
							hinge[i][j] = 0;
						}
					}
				}
			}
		}
		int js = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = i + 1; j <= n; j++)
			{
				if (vis[hinge[i][j]] == 0 && hinge[i][j] != 0)
				{
					vis[hinge[i][j]] = 1;
					js++;
				}
			}
		}
		cout << js << endl;
	}
	return 0;
}